|
Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs". Generic-case complexity is a way of measuring the complexity of a computational problem by neglecting a small set of unrepresentative inputs and considering worst-case complexity on the rest. Small is defined in terms of asymptotic density. The apparent efficacy of generic case complexity is because for a wide variety of concrete computational problems, the most difficult instances seem to be rare. Typical instances are relatively easy. This approach to complexity originated in combinatorial group theory, which has a computational tradition going back to the beginning of the last century. The notion of generic complexity was introduced in 〔I. Kapovich, A. Myasnikov, P. Schupp and V. Shpilrain, ''(Generic case complexity, decision problems in group theory and random walks )'', J. Algebra, vol 264 (2003), 665–694. 〕 where authors showed that for a large class of finitely generated groups the generic time complexity of some classical decision problems from combinatorial group theory, namely the word problem, conjugacy problem and membership problem, are linear. A detailed introduction of generic case complexity can be found in the surveys ,〔 R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''Generic Case Complexity'', unpublished first draft of a book, 143 pages. 〕 〔 R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''(Report on generic case complexity )'', Herald of Omsk University, Special Issue, 2007, 103–110. 〕 == Basic definitions == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Generic-case complexity」の詳細全文を読む スポンサード リンク
|